package greedy;


/**
 * 968. 监控二叉树
 * <p>
 * 给定一个二叉树，我们在树的节点上安装摄像头。
 * <p>
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 * <p>
 * 计算监控树的所有节点所需的最小摄像头数量。
 */
public class N968_BinaryTreeCameras {
    private int count = 0;

    // 0 未覆盖
    // 1 摄像头
    // 2 已覆盖
    public int minCameraCover(TreeNode root) {
        if (traversal(root) == 0) count++;
        return count;
    }

    private int traversal(TreeNode node) {
        if (node == null) return 2; // 节点为空，解释为已覆盖

        int left = traversal(node.left);
        int right = traversal(node.right);

        if (left == 2 && right == 2) return 0;  // 左右子节点都已覆盖，父节点未覆盖，返回 0

        if (left == 0 || right == 0) {  // 左右节点有任意一个未覆盖，父节点装摄像头 返回 1
            count++;
            return 1;
        }

        if (left == 1 || right == 1) return 2;  // 左右节点任意一个是摄像头，父节点已覆盖，返回 2

        return -1;  // 走不到这里的。。。
    }
}
